package aos.voting;

import java.util.Arrays;

public class VotingTree {
	protected int nodeNum;
	protected boolean[] granted;

	public VotingTree(int nodeNum) {
		this.nodeNum = nodeNum;
		granted = new boolean[nodeNum + 1];
	}

	public void clear() {
		Arrays.fill(granted, false);
	}

	public void grant(int nodeId) {
		granted[nodeId + 1] = true;
	}

	public boolean isGranted() {
		return isGranted(1);
	}

	protected boolean isGranted(int nodeId) {
		if (nodeId > nodeNum) {
			return false;
		}
		if (isLeaf(nodeId)) {
			return granted[nodeId];
		}
		boolean l = isGranted(nodeId << 1);
		boolean r = isGranted((nodeId << 1) + 1);
		if (granted[nodeId] && (l || r) || l && r) {
			return true;
		}
		return false;
	}

	protected boolean isLeaf(int nodeId) {
		if (hasLeft(nodeId) || hasRight(nodeId)) {
			return false;
		}
		return true;
	}

	protected boolean hasLeft(int nodeId) {
		if (nodeId << 1 > nodeNum) {
			return false;
		}
		return true;
	}

	protected boolean hasRight(int nodeId) {
		if (nodeId << 1 > nodeNum - 1) {
			return false;
		}
		return true;
	}

	public static void main(String args[]) {
		int nodeNum = 7;
		VotingTree tree1 = new VotingTree(nodeNum);
		VotingTree tree2 = new VotingTree(nodeNum);
		for (int i = 0; i < 1 << nodeNum; ++i) {
			tree1.clear();
			tree2.clear();
			for (int j = 0; j < nodeNum; ++j) {
				if ((i & (1 << j)) != 0) {
					tree1.grant(j);
				} else {
					tree2.grant(j);
				}
			}
			if (tree1.isGranted() && tree2.isGranted()) {
				System.out.println("error");
			}
			if (tree1.isGranted()) {
				System.out.println(Integer.toBinaryString(i));
			}
		}
	}
}
